//
//Copyright GX. Yuan
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//   http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.

/**
 * @file net.go
 * @brief Leetcode practice
 * @details 35. 搜索插入位置
 * @author GX. Yuan  any question please send mail to yuanguanxu@qq.com
 * @date 2021-6-28
 * @version V1.0
 * @attention 硬件平台: windows 10 家庭版
 * SDK版本：Go 1.16.5
 * IDE版本：GoLand 2020.2.3
 */

package main

import "fmt"
func searchInsert(nums []int, target int) int {
	var ans int
	l:=0
	r:=len(nums)-1
	var mid = len(nums)-1
	for l<=r{
		mid=(r-l)>>1+l
		// 首先检查是否动右边的位置，由于右边的位置，始终保持，比目标数大;
		// 如果比目标数大，那么移动位置；否则移动左边，不断逼近。
		// 无论如何变化，右边的值，永远是大于等于目标值;
		// 程序的目的被修改掉了
		// 找到第一个大于等于它的下标;
		// 在一个有序数组中找第一个大于等于 target 的下标;
		if nums[mid]>=target{
			ans=mid
			r=mid-1
		}else{
			l=mid+1
		}
	}
	return ans
}
// 方法二
func searchInsert(nums []int ,target int) int{
	l ,r := 0,len(nums)-1
	var mid int
	for l<=r {
		mid = (r-l)>>1+l
		if nums[mid]<target {
			l=mid+1
		}else {
			r = mid - 1
		}
	}
	return l
}




func main() {
	nums:=[] int{1,3,5,6}
	fmt.Println(searchInsert(nums,3))
}
// 思路：
// 如果找到的情形的话；r=l=mid 一定是这样；